package org.chengn.level_middle.context2415;

import org.chengn.definition.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * @Title: Context2415
 * @Author ChengN
 * @Package org.chengn.level_middle.context2415
 * @Date 2023/12/15 1:32
 * @description: 反转二叉树的奇数层
 */
public class Context2415 {
    public TreeNode reverseOddLevels(TreeNode root) {
        Queue<TreeNode> nodes = new ArrayDeque<>();
        nodes.add(root);
        int height = 0;
        while (!nodes.isEmpty()) {
            int size = nodes.size();
            height++;
            List<TreeNode> list = new ArrayList<>(size * 2);
            for (int i = 0; i < size; ++i) {
                TreeNode node = nodes.poll();
                if (node.left != null) {
                    nodes.add(node.left);
                    if (height % 2 == 1) {
                        list.add(node.left);
                    }
                }
                if (node.right != null) {
                    nodes.add(node.right);
                    if (height % 2 == 1) {
                        list.add(node.right);
                    }
                }
            }
            if (height % 2 == 1) {
                int l = 0, r = list.size() - 1;
                while (l < r) {
                    int tmp = list.get(l).val;
                    list.get(l++).val = list.get(r).val;
                    list.get(r--).val = tmp;
                }
            }
        }
        return root;
    }
}
